﻿#pragma once
class ICountOdds
{
public:
    /**
     * 在区间范围内统计奇数数目
     * https://leetcode.cn/problems/count-odd-numbers-in-an-interval-range/
     * 数学
     *
     * 给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。
     */
    virtual int countOdds(int low, int high) = 0;
};

class CountOddsSolution
{
    class DeltaHalf :ICountOdds
    {
    public:
        int countOdds(int low, int high) override
        {
            if (low == high)
                return (low & 1) != 0 ? 1 : 0;

            if ((low & 1) == 0)
                low++;
            if ((high & 1) == 0)
                high--;

            int n = high - low + 1;
            return n - (n >> 1);
        }
    };

    class PreSum :ICountOdds
    {
    public:
        /**
         * 使用前缀和思想来解决这个问题，定义pre(x)为区间[0,x] 中奇数的个数，很显然：
         * pre(x)=floor(x+1/2);
         * 故答案为pre(high)−pre(low−1)。
         */
        int countOdds(int low, int high) override
        {
            return pre(high) - pre(low - 1);
        }
    private:
        int pre(int x)
        {
            return (x + 1) >> 1;
        }
    };
};